package strategies;

import gamePlay.BFS;
import gamePlay.BFS.SuccessfulSearch;
import gamePlay.MoveManager;
import gamePlay.combat.AlphaBeta;
import gamePlay.combat.Battle;
import gamePlay.combat.BattlesIdentifier;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import stateInfo.Cell;
import stateInfo.GameState;
import utilities.Logger;
import utilities.TimeRunningOutException;
import utilities.Utils;

import com.google.common.base.Optional;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSetMultimap;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;


/**
 * This class contains the ant strategy. It generates all the ant moves.
 */
public abstract class AbstractStrategy {
  
  /**
   * Called by TurnManager.playATurn to play a turn.
   * 
   * Catches exceptions and completes the turn.
   */

	/*public static void playATurn( ) {
    
    final AbstractStrategy strategy = new DiffusionStrategyWithFunctionalWeighting( );
    try {
      strategy.buildOrders( );
    } catch (final TimeRunningOutException e) {
      Logger.log("Caught TimeRunningOutException: " + e.getMessage( ));
      printStackTraceElements(e);
    } catch (final RuntimeException e) {
      Logger.log("Caught RuntimeException: " + e.getMessage( ));
      printStackTraceElements(e);
    } catch (final Exception e) {
      Logger.log("Caught Exception: " + e.getMessage( ));
      printStackTraceElements(e);
    } finally {
      strategy.moveManager.issueOrders( );
    }
  }
  
  */
	
	public static void playATurn( ){
		final AbstractStrategy strategy = new DiffusionStrategyWithFunctionalWeighting( );
		strategy.doTurn();
		
	};
	
	public abstract void doTurn();
	
  protected static void printStackTraceElements(final Exception e) {
    final StackTraceElement[] stacktrace = e.getStackTrace( );
    for (final StackTraceElement ste: stacktrace)
      Logger.log(ste);
  }
  
  @SuppressWarnings("unused")
  private final ImmutableSet<Cell> enemyAnts;
  
  private final ImmutableSet<Cell> enemyHills;
  
  private final ImmutableSet<Cell> food;
  
  /** Store a local reference to the GameState for convenience. */
  public final GameState           gameState;
  
  public final MoveManager         moveManager;
  
  protected final ImmutableSet<Cell> myAnts;
  
  
  public AbstractStrategy( ) {
    
    gameState = GameState.gameState;
    
    enemyAnts = gameState.getEnemyAnts( );
    enemyHills = gameState.getEnemyHills( );
    food = gameState.getFood( );
    myAnts = gameState.getMyAnts( );
    
    moveManager = new MoveManager(myAnts);
  }
  
  
  public ImmutableSet<Cell> availableAnts( ) {
    return moveManager.availableAnts( );
  }
  
  
  /**
   * The primary Strategy method. Runs through the different ways ants may be
   * used and assigns them to various tasks.
   * 
   * TODO: Need to complete combatSupport and areaSupport, including patrolling
   * own territory.
   */
  protected void buildOrders( ) {
    
    Logger.log("Combat");
    combat( );
    
    if (noMoreAnts( )) return;
    searchBackwards(food, 1, "Find food");
    
    if (noMoreAnts( )) return;
    searchBackwards(enemyHills, availableAnts( ).size( ) / 2, "Attack enemy hills");
    
    if (noMoreAnts( )) return;
    // combatSupport( );
    
    if (noMoreAnts( )) return;
    moveAwayFromHills( );
    
    // Set<Cell> onDeckContour = Utils.take(40, gameState.onDeckContour);
    // searchBackwards(onDeckContour, 1, "Explore onDeckContour: " +
    // Utils.prefix(onDeckContour));
    
    if (noMoreAnts( )) return;
    final ImmutableSet<Cell> cellsToExplore = Utils.take(30, cellsToExplore( ));
    searchBackwards(cellsToExplore, (int) (((double) (availableAnts( ).size( ))) / cellsToExplore.size( )) + 2, "Explore: " + Utils.prefix(cellsToExplore));
    
    if (noMoreAnts( )) return;
    Logger.log("\n\t\tRemaining ants");
    // Must do this in case an ant is sitting in a cell that another ant has
    // been ordered to move to.
    moveManager.findValidMovesForRemainingAnts( );
  }
  
  
  /**
   * Exploration with respect to least-recently-seen.
   * 
   * @return
   */
  private Set<Cell> cellsToExplore( ) {
    final ImmutableSetMultimap<Integer, Cell> lastSeenCohorts = gameState.getLastSeenCohorts( );
    final TreeSet<Integer> keysInOrder = new TreeSet<>( );
    keysInOrder.addAll(lastSeenCohorts.keySet( ));
    return getOldReachableCells(lastSeenCohorts, keysInOrder);
  }
  
  
  /**
   * Find battles and generate battle orders.
   * 
   */
  private void combat( ) {
    final ImmutableSet<Battle> battles = BattlesIdentifier.identifyBattles(gameState);
    Logger.log("Battles: " + battles);
    for (final Battle battle: battles) {
      findAndAssignAlphaBetaMoves(battle);
      assignSupportMoves(battle);
    }
  }
  
  
  /**
   * Assign moves to support ants in battles. This is only a partial solution to
   * combatSupport.
   * 
   * @param battle
   */
  private void assignSupportMoves(Battle battle) {
    if (battle.enemyMovedAnts.isEmpty( )) return;
    Logger.log("Assign support ants");
    
    // Backwards BFS from enemyMovedAnts to mySupportAnts
    final List<Cell> openSet = Lists.newArrayList(Sets.newHashSet(battle.enemyMovedAnts));
    final Set<Cell> closedSet = Sets.newHashSet(Sets.newHashSet(battle.enemyMovedAnts));
    
    // Run a multi-seed BFS, where the seeds are the enemyMovedAnts in the
    // Battles. For each of my support ants encountered, have it move toward an
    // enemyMovedAnt.
    while (!openSet.isEmpty( )) {
      final Cell cell = openSet.remove(0);
      for (final Cell neighbor: GameState.gameState.getLandNeighbors(cell)) {
        if (closedSet.contains(neighbor)) continue;
        closedSet.add(neighbor);
        // Any number of support ants may move to an enemy ant.
        openSet.add(neighbor);
        if (battle.mySupportAnts.contains(neighbor) &&
            !moveManager.alreadyAssigned(neighbor)) moveManager.assignOrderIfValid(neighbor, cell, "Support combat");
      }
    }
    
  }
  
  
  /**
   * Call alphaBeta to get ant assigned moves for this Battle.
   * 
   * @param battle
   */
  private void findAndAssignAlphaBetaMoves(Battle battle) {
    final Map<Cell, Cell> moves = AlphaBeta.findBestMoves(battle);
    
    for (final Cell myAnt: moves.keySet( ))
      moveManager.assignOrderIfValid(myAnt, moves.get(myAnt), "Combat");
  }
  
  
  /**
   * Collect cells from least-recently-seen from oldest up until we have enough
   * for availableAnts.
   * 
   * @param lastSeenCohorts
   * @param keysInOrder
   * @return
   */
  private Set<Cell> getOldReachableCells(final ImmutableSetMultimap<Integer, Cell> lastSeenCohorts,
                                         final TreeSet<Integer> keysInOrder) {
    final Set<Cell> toExploreCells = new HashSet<>( );
    while (!keysInOrder.isEmpty( )) {
      final Integer turnNumber = keysInOrder.pollFirst( );
      toExploreCells.addAll(Sets.intersection(lastSeenCohorts.get(turnNumber),
                                              gameState.reachableCells( )));
      if (toExploreCells.size( ) >= availableAnts( ).size( )) break;
    }
    return toExploreCells;
  }
  
  
  /**
   * Move myAnt away from MyHill. Uses MyHillsContour to explore the space.
   * 
   * @param myAnt
   */
  private void moveAway(final Cell myAnt) {
    Cell step = null;
    for (final Cell neighbor: gameState.getLandNonFoodNonCaveNeighbors(myAnt))
      if (step == null
          || gameState.howRemote(neighbor) > gameState.howRemote(step)
          || gameState.howRemote(neighbor) < gameState.howRemote(step) - 20) step = neighbor;
    if (step == null) {
      Logger.log("moveAway: " + myAnt + " is lost in a cave.  No moveAway move.");
      return;
    }
    moveManager.assignOrderIfValid(myAnt,
                                   step,
                                   MoveManager.noGoal,
                                   gameState.howRemote(myAnt) + " -> " + gameState.howRemote(step));
  }
  
  
  /**
   * Move ants away from MyHills using MyHillsContourMap.
   */
  private void moveAwayFromHills( ) {
    Logger.log("\n\t\t" + "moveAwayFromHills");
    
    if (gameState.contourHasBeenExplored( )) {
      Logger.log("Game grid explored.");
      return;
    }
    
    final TreeSet<Cell> myAntsByRemoteness = new TreeSet<>(new Comparator<Cell>( ) {
      
      @Override
      public int compare(final Cell cell_1, final Cell cell_2) {
        return gameState.howRemote(cell_1) - gameState.howRemote(cell_2);
      }
      
    });
    
    myAntsByRemoteness.addAll(availableAnts( ));
    
    int count = 0;
    final Iterator<Cell> remoteAntIterator = myAntsByRemoteness.descendingIterator( );
    while (remoteAntIterator.hasNext( ) && count < 40) {
      moveAway(remoteAntIterator.next( ));
      count++;
    }
  }
  
  
  /**
   * Return true if there are no available ants.
   * 
   * @return
   */
  private boolean noMoreAnts( ) {
    return availableAnts( ).isEmpty( );
  }
  
  
  /**
   * Call the BFS and assign moves based on the result.
   * 
   * @param seeds
   * @param goalsPerSeed
   * @param millis
   * @param message
   */
  private void searchBackwards(final Set<Cell> seeds, final int goalsPerSeed,
                               final int millis, final String message) {
    
    Logger.log("\n\t\t" + message);
    
    // Search "backwards" from food to ants.
    final Set<BFS.SuccessfulSearch> successfulSearches = BFS.search(seeds, availableAnts( ), goalsPerSeed, millis);
    for (final SuccessfulSearch successfulSearch: successfulSearches) {
      // Ants are the goals of the search.
      final Cell myAnt = successfulSearch.goal;
      // Food pellets are the seeds of the search.
      final Cell seed = successfulSearch.seed;
      // If we are next to food, don't move. If we have to move,
      // invertedLastSetp will be present.
      final Cell firstStep = gameState.isFood(seed) && myAnt.isANeighborOf(seed) ? myAnt
                                                                                : myAnt.takeAStep(successfulSearch.invertedLastStep.get( ));
      if (gameState.isFood(firstStep) ||
          !moveManager.assignOrderIfValid(myAnt,
                                          firstStep,
                                          Optional.of(seed),
                                          successfulSearch.message)) {
        // If the order is not valid, the ant won't be assigned here. It will be
        // available to be assigned later. The first step might be food if
        // another ant is assigned to that food and this ant is attempting to
        // move through it.
        Logger.log(myAnt + " to be assigned later.");
      }
    }
  }
  
  
  /**
   * call searchBackwards/4.
   * 
   * @param seeds
   * @param goalsToSeeds
   * @param message
   */
  private void searchBackwards(final Set<Cell> seeds,
                               final int goalsToSeeds,
                               final String message) {
    searchBackwards(seeds, goalsToSeeds, 200, message);
  }
  
  
}
